package arithmetic2.day08;

import java.util.PriorityQueue;

/*
    使用贪心算法求解哈夫曼编码问题:
        数组所有元素的和为金条的总长度L
        每次切割金条需要该金条长度的铜板
        求出切割成数组元素样子的最小代价
 */
public class Greed03 {
    public static void main(String[] args) {
        int arr[] = {10,30,20};
        System.out.println(greed(arr));
    }

    /*
        将所有元素放入小根堆中，每次从小根堆中弹出两个元素结合，代价为两个元素的和
        再将结合的值放回小根堆，直到小根堆只有一个元素为止
     */
    public static int greed(int arr[]) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int num : arr) {
            queue.add(num);
        }
        int sum = 0;
        int temp = 0;
        while (queue.size() > 1) {
            temp = queue.poll() + queue.poll();
            sum += temp;
            queue.add(temp);
        }
        return sum;
    }
}
